import random
from typing import Tuple


def quick_sort(nums):
    if not nums or len(nums) == 0:
        return

    def process(l, r):
        if l >= r: return
        x = nums[random.randint(l, r)]
        board = partition(l, r, x)
        process(l, board[0])
        process(board[1], r)

    def partition(l, r, x):
        # 左边都是 < x, 右边都是 > x。
        # return board[0] = 小于x的最右位置 board[1] = 大于x的最左位置
        i = l
        left_board, right_board = l-1, r+1
        while i < right_board:
            if nums[i] < x:
                left_board += 1
                nums[i], nums[left_board] = nums[left_board], nums[i]
                i += 1
            elif nums[i] > x:
                right_board -= 1
                nums[i], nums[right_board] = nums[right_board], nums[i]
                # 从右边过来的数，还要继续看
            else:
                i += 1
        return (left_board, right_board)

    process(0, len(nums) - 1)

def test(n: int, ranges: Tuple[int, int], t: int):
    '''
    测试函数
    :param n: 测试数组长度
    :param maximum: 生成数组元素的大小范围
    :param t: 测试轮数
    '''
    for _ in range(t):
        arr1 = [random.randint(ranges[0], ranges[1]) for _ in range(n)]
        arr2 = arr1[:]
        arr3 = arr1[:]
        quick_sort(arr2)
        arr3.sort()
        passed = arr2 == arr3
        if not passed:
            print('error!!!')
            print(arr1)
            print(arr2)
            print(arr3)


if __name__ == '__main__':
    arr = random.sample(range(100), 10)
    print(arr)
    quick_sort(arr)
    print(arr)
    print("测试开始")
    test(1000, (-1000, 1000), 100)
    print("测试结束")
